package msb.class07;

import java.util.*;

/**
 * 小根堆
 *
 * @param <T>
 */
public class Heap<T> {
    public List<T> list;
    public Map<T, Integer> map;
    public Comparator<T> comparator;

    public Heap(Comparator<T> comparator) {
        this.list = new ArrayList<>();
        this.map = new HashMap<>();
        this.comparator = comparator;
    }

    public Heap(Comparator<T> comparator, T[] arrT) {
        this.list = Arrays.asList(arrT);
        this.comparator = comparator;
        this.map = new HashMap<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            heapify(i);
        }
    }


    /**
     * 添加
     *
     * @param o
     */
    public void push(T o) {
        list.add(o);
        map.put(o, list.size() - 1);
        heapInsert(list.size() - 1);
    }

    /**
     * 返回堆顶-弹出
     *
     * @return
     */
    public T pop() {
        if (list.size() == 0) {
            throw new RuntimeException();
        }


        //获取堆顶
        T o = list.get(0);
        if (list.size() == 1) {
            map.clear();
            list.clear();
        } else {
            list.set(0, list.get(list.size() - 1));
            list.remove(list.size() - 1);
            map.remove(o);
            map.put(list.get(0), 0);
            heapify(0);
        }
        return o;
    }

    /**
     * 返回堆顶不弹出
     *
     * @return
     */
    public T peek() {
        if (list.size() == 0) {
            return null;
        } else {
            return list.get(0);
        }
    }

    /**
     * 删除
     * 1. 最后一位 -> 删除list和map
     * 2. 非最后一位 -> 最后一位交换 -> 删除list和map -> resign
     *
     * @param o
     */
    public void remove(T o) {
        if (map.containsKey(o)) {
            int index = map.get(o);
            //当前就是最后一个,直接删除
            if (index == list.size() - 1) {
                list.remove(o);
                map.remove(o);
            } else {
                swap(index, list.size() - 1);
                list.remove(o);
                map.remove(o);
                resign(index);
            }
        }
    }

    /**
     * 重排序
     * 要么向上，要么向下
     */
    public void resign(int index) {
        heapify(index);
        heapInsert(index);
    }

    public void resign(T o) {
        int index = map.get(o);
        resign(index);
    }


    /**
     * 堆排序
     */
    public List<T> sort() {
        List<T> sortList = new ArrayList<>();
        for (int i = list.size() - 1; i > 0; i--) {
            sortList.add(peek());
        }
        return sortList;
    }

    public boolean contain(T o) {
        return map.containsKey(o);
    }

    public int size() {
        return list.size();
    }

    /**
     * 堆结构父节点
     * 0的父节点也是0
     */
    private static int parent(int i) {
        return Math.max(((i + 1) / 2 - 1), 0);
    }

    private static int leftChild(int i) {
        return i * 2 + 1;
    }

    private static int rightChild(int i) {
        return i * 2 + 2;
    }

    /**
     * index位置向下沉
     *
     * @param index
     */
    private void heapify(int index) {
        // 有孩子
        while (leftChild(index) < list.size()) {
            // ->取孩子最小值
            // 1.左右孩子都小于heapSize，取左右孩子的最小值
            // 2.只有左孩子，取左孩子
            T minChild = rightChild(index) < list.size() ?
                    comparator.compare(list.get(leftChild(index)), list.get(rightChild(index))) < 0 ?
                            list.get(leftChild(index)) : list.get(rightChild(index)) :
                    list.get(leftChild(index));
            int minChildIndex = rightChild(index) < list.size() ?
                    comparator.compare(list.get(leftChild(index)), list.get(rightChild(index))) < 0 ?
                            leftChild(index) : rightChild(index) :
                    leftChild(index);
            if (comparator.compare(minChild, list.get(index)) < 0) {
                swap(index, minChildIndex);
                index = minChildIndex;
            } else {
                break;
            }
        }
    }


    /**
     * 堆结构
     * index位置向上浮
     * 判断是否小于父节点，大于则交换
     */
    public void heapInsert(int index) {
        while (comparator.compare(list.get(index), list.get(parent(index))) < 0) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private void swap(int i, int j) {
        try {
            if (i == j) {
                return;
            }
            T ti = list.get(i);
            T tj = list.get(j);
            list.set(i, tj);
            list.set(j, ti);
            map.put(list.get(i), i);
            map.put(list.get(j), j);
        } catch (Exception e) {
            throw e;
        }
    }
}
